package _112PathSum;

public class CSolution {

  public static void main(String[] args) {
    System.out.println("aa");
    CSolution cSolution = new CSolution();
    TreeNode treeNode = new TreeNode(5);
    TreeNode treeNode1 = new TreeNode(4);
    TreeNode treeNode2 = new TreeNode(8);
    TreeNode treeNode3 = new TreeNode(11);
    TreeNode treeNode4 = new TreeNode(13);
    TreeNode treeNode5 = new TreeNode(4);
    TreeNode treeNode6 = new TreeNode(7);
    TreeNode treeNode7 = new TreeNode(2);
    TreeNode treeNode8 = new TreeNode(1);
    treeNode.left = treeNode1;
    treeNode1.left = treeNode3;
    treeNode3.left = treeNode6;
    treeNode3.right = treeNode7;
    treeNode.right = treeNode2;
    treeNode2.left = treeNode4;
    treeNode2.right = treeNode5;
    treeNode5.right = treeNode8;
    System.out.println(cSolution.sum(treeNode, 28));
  }

  private boolean sum(TreeNode node, int target) {
    int sum = 0;
    return getSum(node, sum, target);
  }

  private boolean getSum(TreeNode node, int sum, int target) {
    if (node == null) {
      return false;
    }
    sum = sum + node.val;
    if (sum == target) {
      return true;
    }
    if (sum > target) {
      return false;
    }
    return getSum(node.left, sum, target) || getSum(node.right, sum, target);
  }
}
